SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>One-way function</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">One-way function</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:1px solid #a2a9b1;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("./mw/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}

/* end https://en.wikipedia.org/ */

</style>

<div><span class="unsolved-label" id="unsolved-label-computer_science">Unsolved problem in computer science</span></div>

<div class="unsolved-body">Do one-way functions exist?</div>

<div class="unsolved-more"><a href="List_of_unsolved_problems_in_computer_science" title="List of unsolved problems in computer science">More unsolved problems in computer science</a></div>

</div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>one-way function</b> is a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> that is easy to compute on every input, but hard to <a href="Inverse_function" title="Inverse function">invert</a> given the <a href="Image_(mathematics)" title="Image (mathematics)">image</a> of a random input. Here, "easy" and "hard" are to be understood in the sense of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, specifically the theory of <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> problems. This has nothing to do with whether the function is <a href="One-to-one_function" class="mw-redirect" title="One-to-one function">one-to-one</a>; finding any one input with the desired image is considered a successful inversion. (See <a href="#Theoretical_definition">§ Theoretical definition</a>, below.)

</p><p>The existence of such one-way functions is still an open <a href="Conjecture" title="Conjecture">conjecture</a>. Their existence would prove that the <a href="Complexity_classes" class="mw-redirect" title="Complexity classes">complexity classes</a> <a href="P_%3D_NP_problem" class="mw-redirect" title="P = NP problem">P and NP are not equal</a>, thus resolving the foremost unsolved question of theoretical computer science.<sup id="cite_ref-Goldreich_1-0" class="reference"><a href="#cite_note-Goldreich-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: ex. 2.2, page 70">: ex. 2.2, page 70 </span></sup> The converse is not known to be true, i.e. the existence of a proof that P ≠ NP would not directly imply the existence of one-way functions.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any <a href="Black_hat_hacking" class="mw-redirect" title="Black hat hacking">malicious agents</a>". One-way functions, in this sense, are fundamental tools for <a href="Cryptography" title="Cryptography">cryptography</a>, <a href="Personal_identification" class="mw-redirect" title="Personal identification">personal identification</a>, <a href="Authentication" title="Authentication">authentication</a>, and other <a href="Data_security" title="Data security">data security</a> applications. While the existence of one-way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most <a href="Telecommunications" title="Telecommunications">telecommunications</a>, <a href="E-commerce" title="E-commerce">e-commerce</a>, and <a href="Online_banking" title="Online banking">e-banking</a> systems around the world.

</p>

<div class="mw-heading mw-heading2"><h2 id="Theoretical_definition">Theoretical definition</h2></div>

<p>A function <i>f</i> : {0, 1}<sup>*</sup> → {0, 1}<sup>*</sup> is <b>one-way</b> if <i>f</i> can be computed by a polynomial-time algorithm, but any polynomial-time <a href="Randomized_algorithm" title="Randomized algorithm">randomized algorithm</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math></span><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"></span> that attempts to compute a pseudo-inverse for <i>f</i> succeeds with <a href="Negligible_function" title="Negligible function">negligible</a> probability. (The * superscript means any number of repetitions, see <a href="Kleene_star" title="Kleene star">Kleene star</a>.) That is, for all randomized algorithms <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math></span><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"></span>, all positive integers <i>c</i> and all sufficiently large <i>n</i> = length(<i>x</i>),

</p>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}</annotation>

</semantics>

</math></span><img src="./bcabaaa7ff3f11fc73cf28f81878880173d1f3da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.722ex; height:3.009ex;" alt="{\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}" loading="lazy"></span></dd></dl>

<p>where the probability is over the choice of <i>x</i> from the <a href="Uniform_distribution_(discrete)" class="mw-redirect" title="Uniform distribution (discrete)">discrete uniform distribution</a> on {0, 1} <sup><i>n</i></sup>, and the randomness of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math></span><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"></span>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>Note that, by this definition, the function must be "hard to invert" in the <a href="Best%2C_worst_and_average_case" title="Best, worst and average case">average-case, rather than worst-case</a> sense. This is different from much of complexity theory (e.g., <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hardness</a>), where the term "hard" is meant in the worst-case. That is why even if some candidates for one-way functions (described below) are known to be <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>, it does not imply their one-wayness. The latter property is only based on the lack of known algorithms to solve the problem.

</p><p>It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function that outputs the string of <i>n</i> zeros on any input of length <i>n</i> is <i>not</i> a one-way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm <i>F</i> that just outputs any string of length <i>n</i> on input <i>f</i>(<i>x</i>) will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.

</p>

<div class="mw-heading mw-heading2"><h2 id="Related_concepts">Related concepts</h2></div>

<p>A <b>one-way permutation</b> is a one-way function that is also a permutation—that is, a one-way function that is <a href="Bijective" class="mw-redirect" title="Bijective">bijective</a>. One-way permutations are an important <a href="Cryptographic_primitive" title="Cryptographic primitive">cryptographic primitive</a>, and it is not known if their existence is implied by the existence of one-way functions.

</p><p>A <a href="Trapdoor_one-way_function" class="mw-redirect" title="Trapdoor one-way function">trapdoor one-way function</a> or trapdoor permutation is a special kind of one-way function. Such a function is hard to invert unless some secret information, called the <i>trapdoor</i>, is known.

</p><p>A <b>collision-free hash function</b> <i>f</i> is a one-way function that is also <i>collision-resistant</i>; that is, no <a href="Randomized_polynomial_time" class="mw-redirect" title="Randomized polynomial time">randomized polynomial time</a> algorithm can find a <a href="Hash_collision" title="Hash collision">collision</a>—distinct values <i>x</i>, <i>y</i> such that <i>f</i>(<i>x</i>) = <i>f</i>(<i>y</i>)—with non-negligible probability.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Theoretical_implications_of_one-way_functions">Theoretical implications of one-way functions</h2></div>

<p>If <i>f</i> is a one-way function, then the inversion of <i>f</i> would be a problem whose output is hard to compute (by definition) but easy to check (just by computing <i>f</i> on it). Thus, the existence of a one-way function implies that <a href="FP_(complexity)" title="FP (complexity)">FP</a> ≠ <a href="FNP_(complexity)" title="FNP (complexity)">FNP</a>, which in turn implies that P ≠ NP. However, P ≠ NP does not imply the existence of one-way functions.

</p><p>The existence of a one-way function implies the existence of many other useful concepts, including:

</p>

<ul><li><a href="Pseudorandom_generator" title="Pseudorandom generator">Pseudorandom generators</a></li>

<li><a href="Pseudorandom_function" class="mw-redirect" title="Pseudorandom function">Pseudorandom function</a> families</li>

<li><a href="Commitment_scheme" title="Commitment scheme">Bit commitment schemes</a></li>

<li>Private-key encryption schemes secure against <a href="Adaptive_chosen-ciphertext_attack" title="Adaptive chosen-ciphertext attack">adaptive chosen-ciphertext attack</a></li>

<li><a href="Message_authentication_code" title="Message authentication code">Message authentication codes</a></li>

<li><a href="Digital_signature_scheme" class="mw-redirect" title="Digital signature scheme">Digital signature schemes</a> (secure against adaptive chosen-message attack)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Candidates_for_one-way_functions">Candidates for one-way functions</h2></div>

<p>The following are several candidates for one-way functions (as of April 2009). Clearly, it is not known whether

these functions are indeed one-way; but extensive research has so far failed to produce an efficient inverting algorithm for any of them.

</p>

<div class="mw-heading mw-heading3"><h3 id="Multiplication_and_factoring">Multiplication and factoring</h3></div>

<p>The function <i>f</i> takes as inputs two prime numbers <i>p</i> and <i>q</i> in binary notation and returns their product. This function can be "easily" computed in <a href="Big_O_notation" title="Big O notation"><i>O</i>(<i>b</i><sup>2</sup>)</a> time, where <i>b</i> is the total number of bits of the inputs. Inverting this function requires finding the <a href="Integer_factorization" title="Integer factorization">factors of a given integer</a> <i>N</i>. The best factoring algorithms known run in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}">

<mrow>

<mrow>

<mroot>

<mrow>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mroot>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}</annotation>

</semantics>

</math></span><img src="./fce9dac980e9d4ef0d5ed82aa0172be61d7b57b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:23.223ex; height:6.343ex;" alt="{\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}" loading="lazy"></span>time, where b is the number of bits needed to represent <i>N</i>.

</p><p>This function can be generalized by allowing <i>p</i> and <i>q</i> to range over a suitable set of <a href="Semiprimes" class="mw-redirect" title="Semiprimes">semiprimes</a>. Note that <i>f</i> is not one-way for randomly selected integers <span class="nowrap"><i>p</i>, <i>q</i> > 1</span>, since the product will have 2 as a factor with probability 3/4 (because the probability that an arbitrary <i>p</i> is odd is 1/2, and likewise for <i>q</i>, so if they're chosen independently, the probability that both are odd is therefore 1/4; hence the probability that <i>p</i> or <i>q</i> is even, is <span class="nowrap">1 − 1/4 = 3/4</span>).

</p>

<div class="mw-heading mw-heading3"><h3 id="The_Rabin_function_(modular_squaring)">The Rabin function (modular squaring)</h3></div>

<p>The <b>Rabin function</b>,<sup id="cite_ref-Goldreich_1-1" class="reference"><a href="#cite_note-Goldreich-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 57">: 57 </span></sup> or squaring <a href="Modular_arithmetic" title="Modular arithmetic">modulo</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=pq}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=pq}</annotation>

</semantics>

</math></span><img src="./1efc286342c8aeaa396b1816f62477a680a7b395.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.401ex; height:2.509ex;" alt="{\displaystyle N=pq}" loading="lazy"></span>, where <span class="texhtml mvar" style="font-style:italic;">p</span> and <span class="texhtml mvar" style="font-style:italic;">q</span> are primes is believed to be a collection of one-way functions. We write

</p>

<msub>

<mi>Rabin</mi>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {Rabin} _{N}(x)\triangleq x^{2}{\bmod {N}}}</annotation>

</semantics>

</math></span><img src="./66265b67375a84977248b2990f671a344a590f8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.163ex; height:3.176ex;" alt="{\displaystyle \operatorname {Rabin} _{N}(x)\triangleq x^{2}{\bmod {N}}}" loading="lazy"></span></dd></dl>

<p>to denote squaring modulo <span class="texhtml mvar" style="font-style:italic;">N</span>: a specific member of the <b>Rabin collection</b>. It can be shown that extracting square roots, i.e. inverting the Rabin function, is computationally equivalent to factoring <span class="texhtml mvar" style="font-style:italic;">N</span> (in the sense of <a href="Polynomial-time_reduction" title="Polynomial-time reduction">polynomial-time reduction</a>). Hence it can be proven that the Rabin collection is one-way if and only if factoring is hard. This also holds for the special case in which <span class="texhtml mvar" style="font-style:italic;">p</span> and <span class="texhtml mvar" style="font-style:italic;">q</span> are of the same bit length. The <a href="Rabin_signature_algorithm" title="Rabin signature algorithm">Rabin signature algorithm</a> is based on the assumption that this Rabin function is one-way.

</p>

<div class="mw-heading mw-heading3"><h3 id="Discrete_exponential_and_logarithm">Discrete exponential and logarithm</h3></div>

<p><a href="Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a> can be done in polynomial time. Inverting this function requires computing the <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a>. Currently there are several popular groups for which no algorithm to calculate the underlying discrete logarithm in polynomial time is known. These groups are all <a href="Finite_abelian_group" class="mw-redirect" title="Finite abelian group">finite abelian groups</a> and the general discrete logarithm problem can be described as thus.

</p><p>Let <i>G</i> be a finite abelian group of <a href="Cardinality" title="Cardinality">cardinality</a> <i>n</i>. Denote its <a href="Group_operation" class="mw-redirect" title="Group operation">group operation</a> by multiplication. Consider a <a href="Primitive_element_(finite_field)" title="Primitive element (finite field)">primitive element</a> <span class="nowrap"><i>α</i> ∈ <i>G</i></span> and another element <span class="nowrap"><i>β</i> ∈ <i>G</i></span>. The discrete logarithm problem is to find the positive integer <i>k</i>, where <span class="nowrap">1 ≤ <i>k</i> ≤ n</span>, such that:

</p>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</munder>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha ^{k}=\underbrace {\alpha \cdot \alpha \cdot \ldots \cdot \alpha } _{k\;\mathrm {times} }=\beta }</annotation>

</semantics>

</math></span><img src="./53d55cfd93faa33e1ca8c600149a7b8ea1706bff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:22.329ex; height:6.009ex;" alt="{\displaystyle \alpha ^{k}=\underbrace {\alpha \cdot \alpha \cdot \ldots \cdot \alpha } _{k\;\mathrm {times} }=\beta }" loading="lazy"></span></dd></dl>

<p>The integer <i>k</i> that solves the equation <span class="nowrap"><i>α<sup>k</sup></i> = <i>β</i></span> is termed the <b>discrete logarithm</b> of <i>β</i> to the base <i>α</i>. One writes <span class="nowrap"><i>k</i> = log<sub><i>α</i></sub> <i>β</i></span>.

</p><p>Popular choices for the group <i>G</i> in discrete logarithm <a href="Cryptography" title="Cryptography">cryptography</a> are the cyclic groups <a href="Multiplicative_group_of_integers_modulo_n" title="Multiplicative group of integers modulo n">(<b>Z</b><sub><i>p</i></sub>)<sup><i>×</i></sup></a> (e.g. <a href="ElGamal_encryption" title="ElGamal encryption">ElGamal encryption</a>, <a href="Diffie%E2%80%93Hellman_key_exchange" title="Diffie–Hellman key exchange">Diffie–Hellman key exchange</a>, and the <a href="Digital_Signature_Algorithm" title="Digital Signature Algorithm">Digital Signature Algorithm</a>) and cyclic subgroups of <a href="Elliptic_curve" title="Elliptic curve">elliptic curves</a> over <a href="Finite_field" title="Finite field">finite fields</a> (<i>see</i> <a href="Elliptic_curve_cryptography" class="mw-redirect" title="Elliptic curve cryptography">elliptic curve cryptography</a>).

</p><p>An elliptic curve is a set of pairs of elements of a <a href="Field_(mathematics)" title="Field (mathematics)">field</a> satisfying <span class="nowrap"><i>y</i><sup>2</sup> = <i>x</i><sup>3</sup> + <i>ax</i> + <i>b</i></span>. The elements of the curve form a group under an operation called "point addition" (which is not the same as the addition operation of the field). Multiplication <i>kP</i> of a point <i>P</i> by an integer <i>k</i> (<i>i.e.</i>, a <a href="Group_action_(mathematics)" class="mw-redirect" title="Group action (mathematics)">group action</a> of the additive group of the integers) is defined as repeated addition of the point to itself. If <i>k</i> and <i>P</i> are known, it is easy to compute <span class="nowrap"><i>R</i> = <i>kP</i></span>, but if only <i>R</i> and <i>P</i> are known, it is assumed to be hard to compute <i>k</i>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Cryptographically_secure_hash_functions">Cryptographically secure hash functions</h3></div>

<p>There are a number of <a href="Cryptographic_hash_function" title="Cryptographic hash function">cryptographic hash functions</a> that are fast to compute, such as <a href="SHA-256" class="mw-redirect" title="SHA-256">SHA-256</a>. Some of the simpler versions have fallen to sophisticated analysis, but the strongest versions continue to offer fast, practical solutions for one-way computation. Most of the theoretical support for the functions are more techniques for thwarting some of the previously successful attacks.

</p>

<div class="mw-heading mw-heading3"><h3 id="Other_candidates">Other candidates</h3></div>

<p>Other candidates for one-way functions include the hardness of the decoding of random <a href="Linear_code" title="Linear code">linear codes</a>, the hardness of certain <a href="Lattice_problems" class="mw-redirect" title="Lattice problems">lattice problems</a>, and the <a href="Subset_sum_problem" title="Subset sum problem">subset sum problem</a> (<a href="Naccache%E2%80%93Stern_knapsack_cryptosystem" title="Naccache–Stern knapsack cryptosystem">Naccache–Stern knapsack cryptosystem</a>).

</p>

<div class="mw-heading mw-heading2"><h2 id="Universal_one-way_function">Universal one-way function</h2></div>

<p>There is an explicit function <i>f</i> that has been proved to be one-way, if and only if one-way functions exist.<sup id="cite_ref-HCPred_5-0" class="reference"><a href="#cite_note-HCPred-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> In other words, if any function is one-way, then so is <i>f</i>. Since this function was the first combinatorial complete one-way function to be demonstrated, it is known as the "universal one-way function". The problem of finding a one-way function is thus reduced to proving—perhaps non-constructively—that one such function exists.

</p><p>There also exists a function that is one-way if polynomial-time bounded <a href="Kolmogorov_complexity#Time-bounded_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a> is mildly hard on average. Since the existence of one-way functions implies that polynomial-time bounded Kolmogorov complexity is mildly hard on average, the function is a universal one-way function.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="One-way_compression_function" title="One-way compression function">One-way compression function</a></li>

<li><a href="Cryptographic_hash_function" title="Cryptographic hash function">Cryptographic hash function</a></li>

<li><a href="Geometric_cryptography" title="Geometric cryptography">Geometric cryptography</a></li>

<li><a href="Trapdoor_function" title="Trapdoor function">Trapdoor function</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Goldreich-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Goldreich_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Goldreich_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="Oded_Goldreich" title="Oded Goldreich">Oded Goldreich</a> (2001). Foundations of Cryptography: Volume 1, Basic Tools (<a rel="nofollow" class="external text" href="http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/part2N.ps">draft available</a> from author's site). Cambridge University Press. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-79172-3</bdi>. See also <a rel="nofollow" class="external text" href="http://www.wisdom.weizmann.ac.il/~oded/foc-book.html">wisdom.weizmann.ac.il</a>.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a href="Shafi_Goldwasser" title="Shafi Goldwasser">Goldwasser, S.</a> and <a href="Mihir_Bellare" title="Mihir Bellare">Bellare, M.</a> <a rel="nofollow" class="external text" href="http://cseweb.ucsd.edu/~mihir/papers/gb.html">"Lecture Notes on Cryptography"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html">Archived</a> 2012-04-21 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>. Summer course on cryptography, MIT, 1996–2001.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Many authors view this definition as strong one-way function. A weak one-way function can be defined similarly except that the probability that every adversarial <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math></span><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"></span> fails to invert <i>f</i> is noticeable. However, one may construct strong one-way functions based on weak ones. Loosely speaking, strong and weak versions of one-way function are equivalent theoretically. See Goldreich's Foundations of Cryptography, vol. 1, ch. 2.1–2.3.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFRussell1995" class="citation journal cs1">Russell, A. (1995). "Necessary and Sufficient Conditions for Collision-Free Hashing". <i><a href="Journal_of_Cryptology" title="Journal of Cryptology">Journal of Cryptology</a></i>. <b>8</b> (2): <span class="nowrap">87–</span>99. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00190757">10.1007/BF00190757</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:26046704">26046704</a>.</cite></span>

</li>

<li id="cite_note-HCPred-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-HCPred_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFLevin2003" class="citation journal cs1"><a href="Leonid_Levin" title="Leonid Levin">Levin, Leonid A.</a> (January 2003). "The Tale of One-Way Functions". <i>Problems of Information Transmission</i>. <b>39</b> (39): <span class="nowrap">92–</span>103. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs.CR/0012023">cs.CR/0012023</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1023634616182">10.1023/A:1023634616182</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFLiuPass2020" class="citation arxiv cs1">Liu, Yanyi; Pass, Rafael (2020-09-24). "On One-way Functions and Kolmogorov Complexity". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2009.11514">2009.11514</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CC">cs.CC</a>].</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li>Jonathan Katz and Yehuda Lindell (2007). <i>Introduction to Modern Cryptography</i>. CRC Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58488-551-3</bdi>.</li>

<li><cite id="CITEREFMichael_Sipser1997" class="citation book cs1"><a href="Michael_Sipser" title="Michael Sipser">Michael Sipser</a> (1997). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips"><i>Introduction to the Theory of Computation</i></a></span>. PWS Publishing. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-534-94728-6</bdi>.</cite> Section 10.6.3: One-way functions, pp. 374–376.</li>

<li><cite id="CITEREFChristos_Papadimitriou1993" class="citation book cs1"><a href="Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a> (1993). <i>Computational Complexity</i> (1st ed.). Addison Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-53082-7</bdi>.</cite> Section 12.1: One-way functions, pp. 279–298.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-08" href="https://en.wikipedia.org/wiki/?title=One-way_function&oldid=1304763424">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>